// 反转链表
// 使用一个变量记录前驱pre 一个变量记录后继next 然后不断更新current.next=pre
// 注意:
// 1.头尾节点的处理
// 2.循环时指针引用导致死循环
// 反转链表简单题如何回答
// 在链表的遍历过程中，用pre保存当前节点的前驱节点，将前驱节点变为下次当前节点的后继节点
// 同时原有的next属性被next变量保存，不影响原遍历情况下，完成反转

var reverseList=function(head){
    // 链表0或1个数据时
    if(!head||!head.next) return head;
    // 超过1个数据时
    // 定义变量记录前驱pre 和当前节点cur
    let cur=head;
    let pre=null;
    // 循环 
    while(cur){
        // 定义变量记录后继next
        let next=cur.next;
        // 交换 使当前节点的前驱变为后继
        cur.next=pre;
        // 前移 下一个被操作的节点
        pre=cur;
        cur=next;   
    }
}

// 递归实现
// 注意：
// 1.将第一节点以外的节点递归reverse
// 2.将第一个节点添加到已经reverse的子链之后
// 3.每次需要保存已经 reverse 的链表的头节点和尾节点
var reverseList2 = function (head) {
    // 递归结束条件
    if (head === null || head.next === null) {
      return head;
    }
  
    // 递归反转 子链表
    let newReverseList = reverseList(head.next);
    // 获取原来链表的第 2 个节点 newReverseListTail
    let newReverseListTail = head.next;
    // 调整原来头结点和第 2 个节点的指向
    newReverseListTail.next = head;
    head.next = null;
  
    // 将调整后的链表返回
    return newReverseList;
  };